\section{Desarrollo}

La implementación realizada del programa \textbf{Autocaras} se encarga de dada una imagen nueva ingresada, compararla usando la teoría desarrollada en la sección anterior, contra una base de datos de caras conocidas y determinar a quién corresponde la nueva imagen.

Se decidió utilizar una biblioteca de funciones denominada \textbf{OpenCV} para simplificar y abstraernos de la carga y el guardado de las imágenes que utilizamos.

Describiremos a continuación los puntos más importantes del programa.

\subsection{Remuestreo de imágenes}

Dado que el coste computacional de los algoritmos está ligado fuertemente con la dimensión de la matriz a tratar. Y la dimensión de la matriz se corresponde con el tamaño de la imagen a la cual se le está haciendo el análisis de las componentes principales. Por simplicidad, trabajamos con imágenes que son cuadradas y nuestra base de datos tiene fotos de 500x500 píxeles. 

Si por cada iteración el algoritmo QR toma $\approx O(n^3) $ operaciones, entonces para una imagen de la base tal como está, realiza $\approx 125 000 000$ operaciones mientras que si decidimos submuestrar la imagen para reducir de alguna manera el número de operaciones vemos que se obtienen buenos resultados y que el número de operaciones se reduce drásticamente. Por ejemplo, para una imagen reducida a 32 píxeles de ancho, la cantidad de operaciones realizadas es de $\approx 32 768$. Si bien, al reducir la calidad de la imagen estamos perdiendo definición y por ende, precisión para encontrar los ``parecidos'' vemos que esto es fundamental a la hora de tener en cuenta el tiempo de ejecución del programa. Y esto puede ser crítico cuando contemos con bases de datos con una cantidad de imágenes considerable.

Entonces, es por esto que se decidió implementar dos métodos de reducción de imágenes tratando de conservar la mayor cantidad de información posible. 

\subsubsection{Método ``Naif''}

El presente modo de submuestreo de las imágenes a utilizar por el programa consiste en: si nuestra imagen destino tiene ancho $k$ y la imagen fuente, ancho $n$ ($n \gg k$); en ir rellenando los $k$ píxeles destino tomando de a $\frac{n}{k}$ píxeles de la imagen fuente. En pseudocódigo:
va convergiendo
{\small
\begin{verbatim}
Imagen destino
Imagen fuente

int paso = fuente.ancho / destino.ancho

for(int i = 0; i < destino.ancho; i++)
	destino[i] = fuente[i*paso]
\end{verbatim} }
Por simplicidad en el código se optó por tratar a la imagen como un arreglo de píxeles. En el código real, la imagen se optó por verla como una matriz (aunque internamente OpenCV lo trata como un arreglo). Esta observación, sin embargo, no afecta al funcionamiento del algoritmo empleado.

\subsubsection{Método de los promedios}

El denominado ``método de los promedios'' lo que hace es lo siguiente: igual que en el caso anterior, tenemos una imagen fuente de ancho $n$ y una imagen destino de ancho $k$. Entonces procedemos a dividir la imagen fuente en $k$ celdas de ancho $\frac{n}{k}$ píxeles y lo que hacemos es tomar el valor promedio de la celda, osea, dividimos la suma de todos los elementos de la submatriz por la cantidad de píxeles que conforman la celda y eso guardamos en la imagen destino. En pseudocódigo sería:

{\small
\begin{verbatim}
Imagen destino
Imagen fuente

int paso = destino.ancho / destino.fuente
        int jsrc = 0; 
        int isrc = 0;
// índices para la imagen fuente. i y j se usan para el destino. 
// El isrc y jsrc se ven afectados por el paso.


        for(int i = 0; i < destino.altura; i++){
                isrc = i*paso;
                for(int j = 0; j < destino.ancho; j++){
                        jsrc = j*paso;
                        destino[i,j] = fuente.promedioMatriz(isrc,jsrc, isrc+paso,jsrc+paso);
                }
        }
//donde promedioMatriz(fila0, filan, col0, coln) retorna el promedio
//de la matriz delimitada por:
// fila0/col0   ...   fila0/coln
// ...
// filan/col0   ...   filan/coln
\end{verbatim}}

Como se puede apreciar, en este caso se dejó la versión matricial de la imagen ya que resulta más claro visualizar las submatrices a las que se promedia. 

\pagebreak
Es importante destacar que este método es más complejo que el ``naif'' sin embargo, se logran resultados mucho más refinados. He aquí un ejemplo de una imagen de 500x500 remuestreada a 100x100 con ambos métodos.  


\begin{figure}[htb]
\begin{center}
\includegraphics[]{test_naif.jpg}
\end{center}
\caption[]{Método Naif}  
\end{figure}

\begin{figure}[htb]
\begin{center}
\includegraphics[]{test_prom.jpg}
\end{center}
\caption[]{Método de promedios}  
\end{figure}

Como podemos ver, la imagen que realiza los promedios por bloque es mucho más suave y con mejor definición que el otro método que parece estar bastante nítido en este tamaño. Sin embargo, las diferencias entre ambas técnicas se agrandan cuanto más chico es el tamaño de la imagen a la que se quiere llegar. 

\subsection{Cálculo de Covarianza}
Para realizar el cálculo de covarianza de las imágenes, lo más destacado a mencionar es que al ser una 
matriz simétrica, realizamos solamente las operaciones para calcular los valores en las posiciones
$S_{i,j}$ para los $1 \leq j \leq i \leq n$ y luego simplemente copiamos los elementos $S_{i,j}$ a los va convergiendo $S_{j,i}$ 
reducir aproximadamente a la mitad de los cálculos. Finalmente lo que se hizo fue seguir con la formula
para calcular la matriz deseada:
$$ S = \dfrac{1}{n-1}\sum^n_{i=1} (x_i - \mu)(x_i - \mu)^T$$

\subsection{Cálculo de Autovectores}
Para realizar el método para el cómputo de los autovectores, de la matriz de covarianza, lo que se hizo fue 
utilizar el algoritmo QR. Este es un algoritmo de carácter iterativo, en donde la matriz converge
a una matriz diagonal, que contiene los autovalores de la matriz inicial ordenados en forma decreciente
según su modulo. Así mismo, usando este mismo algoritmo se puede calcular los autovectores de la matriz. Haciendo
el método iterativo explicado a continuación, la matriz $Q$ converge a una matriz que en sus columna se encuentran
los autovectores de la matriz original, asociados en el mismo orden que los autovalores de la otra matriz resultante.

A continuación se muestra un pseudo-código del método.

{\small
\begin{verbatim}
  [Autovectores, Autovalores] = autocalcular(Matriz A) {
    Matriz autovectores = MatrizIdentidad(a.tamaño);
    Mientras (A.trianguloInferior().suma() > delta) {
      [Matriz R, Matriz Q] = A.factorizarQR();
      autovectores = autovectores*Q;
      A = R*Q;
    }
    Autovalores = A;
  }
\end{verbatim}}

Como se puede ver, siendo el algoritmo un método iterativo, se necesitaba poner un freno para que salga del ciclo.
Se opto por ver cuán 'cerca de ser diagonal' está $A$, y para esto se suma todo el triangulo inferior
de la matriz actual (sin incluir la diagonal) y se ve si es menor a un $\delta$ deseado.

Otro punto importante en este método es el de factorización QR. Estábamos familiarizados con dos métodos, el
método de \emph{Givens} y el método de \emph{Householder}, pero en este caso y viendo que la matriz a calcular no era una matriz
rala, era claramente conveniente utilizar el método de Householder, ya que este va poniendo ceros de
a columnas, a diferencia de Givens que lo va haciendo de a posiciones. En la siguiente apartado se detalla
el método elegido.

\subsubsection{Factorización QR: Método de Householder}

La idea de este método es encontrar dos matriz Q ortogonal y R triangular superior, tales que $A = QR$. Lo que 
propone el método de Householder es ir reflejando las columnas de la matriz para ir triangulando la matriz. El
algoritmo es principalmente el siguiente:

\begin{verbatim}
  [Q, R] = factorizarQR(Matriz A) {
    Matriz Q = MatrizIdentidad(a.tamaño);
    para i en [0..a.tamaño) {
      Matriz Qi = matrizHouseHolderEnColumna(A, i);
      A = Qi*A;
    }
    Q = transpuesta(Q);
    R = A;
  }
\end{verbatim}

Como vemos el algoritmo llama a una función llamada \texttt{matrizHouseHolderEnColumna}, que dado una matriz y una columna
devuelve la matriz que refleja como queremos, toda la columna en $A$, estas son las llamadas \emph{matrices de Householder}.

Un punto importante en este algoritmo, es que a pesar de ser numéricamente estable, luego de cada multiplicación
de la matriz de Householder, se propaga un pequeño error en las cuentas, pero como sabemos que tipo de resultado
debe dar bajo la columna que se esta aplicando, lo que hacemos es forzar a que quede en 0. Luego el código del
algoritmo queda de la siguiente manera:

{\small
\begin{verbatim}
  [Q, R] = factorizarQR(Matriz A) {
    Matriz Q = MatrizIdentidad(a.tamaño);
    para i en [0..a.tamaño) {
      Matriz Qi = matrizHouseHolderEnColumna(A, i);
      A = Qi*A;
      para j en [i+1..a.tamaño) {
        A(i,j) = 0;
      }
    }
    Q = transpuesta(Q);
    R = A;
  }
\end{verbatim}}

\subsection{Transformación Característica}

La idea de la trasformación característica es reducir la cantidad de coordenadas de las variables usadas, para
solamente hacer los cálculos sobre los datos más importantes de las mismas. Entonces lo que se hace es, basado
en los autovectores asociados al los autovalores de máximo valor absoluto, se toman los primeros $k$ autovectores
más importantes y se realiza el siguiente algoritmo:

\begin{verbatim}
  [Array salida] = transformacionCaracteristica(Matriz autovectores, Array entrada, int cantidadCoordenadas) {
    para i en [0..cantidadCoordenadas) {
      double valor = 0;
      para j en [0..autovectores.tamaño) {
        valor = autovectores(i,j)*entrada[j];
      }
      salida[i] = valor;
    }
  }
\end{verbatim}

\subsection{Pertenencia de grupos: Distancia de Mahalanobis}
Para poder decir a que grupo pertenecía la imagen se debía implementar algún algoritmo que analice las distancias
entre la nueva imagen (su transformación característica) y la de las ya cargadas en la base de datos. Para esto
se decidió utilizar la \emph{distancia de Mahalanobis} ya que es muy útil cuando se quiere comparar varios 
conjuntos de datos y un nuevo dato agregado, que es justamente nuestro caso. Este método es útil ya que utiliza las 
correlaciones que hay entre los elementos de un mismo grupo de datos, y basado en eso se calcula una distancia.

A continuación se detalla un pseudo-código del método:

{\small
\begin{verbatim}
  [Grupo] = mahalanobis(Imagen nueva, Álbum base) {
    array distancias[base.cantidadGrupos];
    para cada grupo G en la base {
      Matriz cov = calcularCovarizana(G);
      cov.invertir();
      nueva = nueva-promedio(G);
      distancia[g] = raiz2(nueva*cov*transpuesta(nueva));
    }
    Grupo = indiceDelMinimoValor(distancia);
  }
\end{verbatim}}
